package com.heima.leetcode.datastructure.linkedlist;

/**
 * 有序链表去重复节点， 重复的元素留一个
 */

public class DeleteDuplicates {

    /**
     * <h3>方法一</h3>
     * 删除链表中的重复节点
     * @param head 旧链表的头节点
     * @return 删除重复节点后的头节点
     */
    public static ListNode deleteDuplicates1(ListNode head){
        // 节点数 < 2
        if (head == null || head.next == null){
            return head;
        }
        ListNode p1 = head;
        ListNode p2;
        while ((p2 = p1.next) != null){
            // p1和p2重复，则删除p2，p2后移
            if (p1.val == p2.val){
                p1.next = p2.next;
            } else {
                // p1和p2不重复，p1，p2后移
                p1 = p1.next;
            }
        }
        return head;
    }

    /**
     * <h3>方法二，递归</h3>
     * 用递归方法删除链表中的重复节点，递归永远删除的两个重复节点中后一个节点，所以不需要哨兵节点，而且能处理索引0和1重复的情况
     * @param head 旧链表的头节点
     * @return 删除重复节点后的头节点
     */
    public static ListNode deleteDuplicates2(ListNode head){
        // 递的时候以最后一个节点为终止条件，顺便处理特殊情况
        if (head == null || head.next == null){
            return head;
        }
        ListNode nextHead = deleteDuplicates2(head.next);
        // 归的时候判断当前递归节点和上一次归的节点的值是否相等
        if (head.val == nextHead.val){
            // 相等，则删除上一次归的节点
            head.next = nextHead.next;
        } else {
            // 不相等，则把当前节点纳入已处理范围
            head.next = nextHead;
        }
        // 返回已处理部分的头节点
        return head;
    }
}
